package LeetCode;

import java.util.Stack;

public class LC_445_AddTwoNumbersII {

    public static void main(String[] args) {

    }

    static class ListNode {
        int val;
        ListNode next;

        ListNode(int x) {
            val = x;
        }
    }

    static class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            if (l1 == null) return l2;
            if (l2 == null) return l1;
            Stack<Integer> s1 = new Stack<>();
            Stack<Integer> s2 = new Stack<>();
            while (l1 != null) {
                s1.push(l1.val);
                l1 = l1.next;
            }
            while (l2 != null) {
                s2.push(l2.val);
                l2 = l2.next;
            }
            int sum = 0;
            ListNode curNode = new ListNode(0);
            while (!s1.isEmpty() || !s2.isEmpty()) {
                if (!s1.isEmpty())
                    sum += s1.pop();
                if (!s2.isEmpty())
                    sum += s2.pop();
                ListNode head = new ListNode(sum / 10);
                curNode.val = sum % 10;
                head.next = curNode;
                curNode = head;
                sum /= 10;
            }
            if (curNode.val == 0)
                curNode = curNode.next;
            return curNode;
        }

    }
}